package l.l.w.leetcode.Sum_3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * LeetCode 第12题
 * Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

 For example, given array S = {-1 2 1 -4}, and target = 1.

 The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
 */
public class Sum_3 {
    /**
     * 时间复杂度比较高，有n3
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        for(int i=0;i<n-2;++i){
            if(nums[i]>0 ) continue;
            if(i > 0 && nums[i] == nums[i - 1])continue;    //可以减少一部分计算量
            for(int j=i+1;j<n-1;++j){
                if(nums[i]+nums[j] >0) continue;            //可以减少计算量
                for(int k=j+1;k<n;++k){
                    if(nums[i]+nums[j]+nums[k]==0){
                        List<Integer> list = Arrays.asList(nums[i],nums[j],nums[k]);
                        if(!result.contains(list)){
                            result.add(list);
                        }
                    }
                }
            }
        }
        return result;
    }

    public List<List<Integer>> threeSum_new(int[] nums){
        Arrays.sort(nums);
        ArrayList<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        for( int i = 0; i < n-2; i++){
            if(nums[i] > 0) continue;
            if(i >= 1 && nums[i] == nums[i-1]) continue;
            int target = 0 - nums[i];
            int j = i+1, k = n-1;
            while(j < k){
                int sum = nums[j]+nums[k];
                if(sum == target){
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);
                    result.add(list);
                    j++;
                    k--;
                    while(j <= k && nums[j] == nums[j-1]) j++;
                    while(j<= k && nums[k] == nums[k+1]) k--;
                }else if(sum < target){
                    j++;
                }else{
                    k--;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
//        int[] nums = {-1,0,1,2,-1,-4};
        int[] nums = {0,0,0,0};
        List<List<Integer>> result = new Sum_3().threeSum_new(nums);
        System.out.println(result);
    }
}
